﻿using System.Collections.Generic;
using DefaultNamespace;
using UnityEngine;

public class Octree
{
    public OctreeNode RootNode;
    public List<OctreeNode> emptyLeaves = new List<OctreeNode>();
    public Graph navigationGraph; // 图标的链接

    public Octree(GameObject[] worldObjects, float minNodeSize, Graph navigraph)
    {
        // bounds碰撞体边界
        Bounds bounds = new Bounds();
        navigationGraph = navigraph;
        foreach (var go in worldObjects)
        {
            // 将一个现有的 Bounds 对象扩展，使其能够包含另一个 Bounds 对象
            // 目的是吧这些象限画出来
            bounds.Encapsulate(go.GetComponent<Collider>().bounds);
        }

        // 将矩形变成正方体，便于划分和计算
        float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z });
        Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize) * 1f;
        // bounds.center-sizeVector:
        bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector);

        // 根节点
        RootNode = new OctreeNode(bounds, minNodeSize, null);
        AddObjects(worldObjects);
        GetEmptyLeaves(RootNode);
        ConnectLeafNodeNeighbours();
        // ProcessExtraConnections();
    }

    public int FindBindingNode(OctreeNode node,Vector3 position)
    {
        int found = -1;
        if (node == null) return -1;
        if (node.children == null)
        {
            if (node.nodeBounds.Contains(position)&& node.containedObjects.Count == 0)
            {
                return node.Id;
            }
        }
        else
        {
            for (int i = 0; i < 8; i++)
            {
                found = FindBindingNode(node.children[i],position);
                if (found != -1)
                {
                    break;
                }
            }
        }
        return found;
    }

    // 填充空树叶
    public void GetEmptyLeaves(OctreeNode node)
    {
        if (node == null)
        {
            return;
        }

        if (node.children == null)
        {
            // 若节点不包含物体则视为空叶子
            if (node.containedObjects.Count == 0)
            {
                emptyLeaves.Add(node);
                navigationGraph.AddNode(node);
            }
        }
        else
        {
            for (int i = 0; i < 8; i++)
            {
                GetEmptyLeaves(node.children[i]);

                // 绘制导航图
                // for (int j = 0; j < 8; j++)
                // {
                //     if (j != i)
                //     {
                //         // navigationGraph.AddEdge(node.children[i], node.children[j]);
                //     }
                // }
            }
        }
    }

    public void AddObjects(GameObject[] worldObjects)
    {
        foreach (var go in worldObjects)
        {
            RootNode.AddObjects(go);
        }
    }
    public int AddDestination(Vector3 destination)
    {
        return FindBindingNode(RootNode, destination);
    }
    private void ProcessExtraConnections()
    {
        Dictionary<int, int> subGraphConnections = new Dictionary<int, int>();
        foreach (OctreeNode i in emptyLeaves)
        {
            foreach (OctreeNode j in emptyLeaves)
            {
                if (i.Id != j.Id && i.parent.Id != j.parent.Id)
                {
                    RaycastHit hit;
                    Vector3 dir = j.nodeBounds.center - i.nodeBounds.center;
                    float accuracy = 1;
                    if (!Physics.SphereCast(i.nodeBounds.center, accuracy, dir, out hit))
                    {
                        if (subGraphConnections.TryAdd(i.Id, j.Id))
                        {
                            navigationGraph.AddEdge(i, j);
                        }
                    }
                }
            }
        }
    }

    // 遍历所有空节点
//     void ConnectLeafNodeNeighbours()
//     {
//         List<Vector3> rays = new List<Vector3>()
//         {
//             new Vector3(1, 0, 0), new Vector3(0.707f, 0.707f, 0), new Vector3(0.707f, -0.707f, 0),
//             new Vector3(-1, 0, 0), new Vector3(-0.707f, 0.707f, 0), new Vector3(-0.707f, -0.707f, 0),
//             new Vector3(0, 1, 0), new Vector3(0, 0.707f, 0.707f), new Vector3(0, -0.707f, 0.707f),
//             new Vector3(0, -1, 0), new Vector3(0, -0.707f, -0.707f), new Vector3(0, 0.707f, -0.707f),
//             new Vector3(0, 0, 1), new Vector3(0.707f, 0, 0.707f), new Vector3(-0.707f, 0, 0.707f),
//             new Vector3(0, 0, -1), new Vector3(-0.707f, 0, -0.707f), new Vector3(0.707f, 0, -0.707f),
//         };
//
//         for (int i = 0; i < emptyLeaves.Count; i++)
//         {
//              List<OctreeNode> neighbours = new List<OctreeNode>();
//             
//             for (int j = i + 1; j < emptyLeaves.Count; j++)
//             {
//                 for (int r = 0; r < rays.Count; r++)
//                 {
//                     Ray ray = new Ray(emptyLeaves[i].nodeBounds.center, rays[r].normalized);
//                     float maxLength = emptyLeaves[i].nodeBounds.size.y / 2.0f +
//                                       emptyLeaves[j].nodeBounds.size.y / 2.0f + 0.01f;
//                     float hitLength;
//                     if (emptyLeaves[j].nodeBounds.IntersectRay(ray, out hitLength) && hitLength < maxLength)
//                     {
//                         neighbours.Add(emptyLeaves[j]);
//                         navigationGraph.AddEdge(emptyLeaves[i], emptyLeaves[j]);
//                         break;
//                     }
//                 }
//             }
//              Debug.Log("neighbours: " + neighbours.Count);
//             
//         }
//     }
// }
    void ConnectLeafNodeNeighbours()
    {
        List<Vector3> rays = new List<Vector3>()
        {
            new Vector3(1, 0, 0),
            new Vector3(-1, 0, 0),
            new Vector3(0, 1, 0),
            new Vector3(0, -1, 0),
            new Vector3(0, 0, 1),
            new Vector3(0, 0, -1),
        };

        for (int i = 0; i < emptyLeaves.Count; i++)
        {
            List<OctreeNode> neighbours = new List<OctreeNode>();
            for (int j = 0; j < emptyLeaves.Count; j++)
            {
                if (i != j)
                {
                    for (int r = 0; r < 6; r++)
                    {
                        Ray ray = new Ray(emptyLeaves[i].nodeBounds.center, rays[r]);
                        float maxLength = emptyLeaves[i].nodeBounds.size.y / 2.0f + 0.01f; // 检测距离
                        float hitLength;
                        if (emptyLeaves[j].nodeBounds.IntersectRay(ray, out hitLength))
                        {
                            if (hitLength < maxLength)
                            {
                                neighbours.Add(emptyLeaves[j]);
                            }
                        }
                    }
                }
            }

            foreach (OctreeNode n in neighbours)
            {
                navigationGraph.AddEdge(emptyLeaves[i], n);
            }
        }
    }
}

public class OctreeNode
{
    public Bounds nodeBounds;
    public OctreeNode[] children = null;
    public int Id;
    public List<OctreeObject> containedObjects = new List<OctreeObject>();

    private Bounds[] childBounds;
    private float minSize;
    public OctreeNode parent;

    public OctreeNode(Bounds b, float minNodeSize, OctreeNode parent)
    {
        Id = Utils.id_number++;
        this.parent = parent;
        nodeBounds = b;
        minSize = minNodeSize;
        // quarter :四分之一
        float quarter = nodeBounds.size.y / 4;
        float childLength = nodeBounds.size.y / 2;
        Vector3 childSize = new Vector3(childLength, childLength, childLength);
        // 绘制孩子
        childBounds = new Bounds[8];
        childBounds[0] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, -quarter), childSize);
        childBounds[1] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, quarter), childSize);
        childBounds[2] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, -quarter), childSize);
        childBounds[3] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, quarter), childSize);
        childBounds[4] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, -quarter), childSize);
        childBounds[5] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, quarter), childSize);
        childBounds[6] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, -quarter), childSize);
        childBounds[7] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, quarter), childSize);
    }

    public void AddObjects(GameObject go)
    {
        DivideAndAdd(go);
    }



    // 分割
    public void DivideAndAdd(GameObject go)
    {
        OctreeObject OctObject = new OctreeObject(go);

        if (nodeBounds.size.y <= minSize)
        {
            containedObjects.Add(OctObject);
            return;
        }

        if (children == null)
        {
            children = new OctreeNode[8];
        }

        bool dividing = false;
        for (int i = 0; i < 8; i++)
        {
            if (children[i] == null)
            {
                children[i] = new OctreeNode(childBounds[i], minSize, this);
            }

            if (childBounds[i].Intersects(OctObject.bounds))
            {
                dividing = true;
                children[i].DivideAndAdd(go);
            }
        }

        if (!dividing)
        {
            // 若没被分割，则物体物体就在节点内
            containedObjects.Add(OctObject);
            children = null;
        }
    }

    public void Draw()
    {
        Gizmos.color = new Color(0, 1, 0);
        Gizmos.DrawWireCube(nodeBounds.center, nodeBounds.size);
        Gizmos.color = new Color(1, 1, 0);
        foreach (var obj in containedObjects)
        {
            Gizmos.DrawCube(obj.bounds.center, obj.bounds.size);
        }

        if (children != null)
        {
            for (int i = 0; i < 8; i++)
            {
                if (children[i] != null)
                {
                    children[i].Draw();
                }
            }
        }
        else if (containedObjects.Count != 0) // 说明是叶子节点
        {
            Gizmos.color = new Color(0, 1, 1, 0.25f);
            Gizmos.DrawCube(nodeBounds.center, nodeBounds.size);
        }
    }
}


public class OctreeObject
{
    public Bounds bounds;
    public GameObject gameObject;

    public OctreeObject(GameObject go)
    {
        bounds = go.GetComponent<Collider>().bounds;
        gameObject = go;
    }
}